1. Field of the Invention
The present invention relates to a multiplying method and apparatus, and more particularly to the methods and the apparatuses for adding a partial product and for performing a floating point multiplication.
2. Description of the Related Art
The description will be oriented to (1) addition of partial products, (2) detection of the most significant digit, and (3) normalizing shift implementation in the prior art.
At first, the conventional addition of partial products will be described below. The addition of partial products executed in a sum of products or a multiplication may take a Booth decoding operation for the purpose of reducing the number of partial products and thereby speeding up the addition of partial products. The Booth decoding operation has been discussed in :David A. Patterson, John L. Hennessy, "Computer Architecture A Quantitative Approach", A42 to A44, for example. Later, as an example, consider a multiplication of fractions of a double-precision format defined in ANSI/IEEE Std 754. The fraction is represented in binary notation.
Concretely, with reference to FIGS. 6 to 8, the description will be expanded on the assumption that a 53-digit multiplicand is X, a 53-digit multiplier is Y, and Y is decoded with X. FIG. 6 shows inputs to a Booth decoder. As shown, the operation is executed to range the 53-digit Y (implicit `1` (the most significant digit of the fraction which is omitted), Y1, Y2, . . . , Y52) from the left digit, decode each three digits of the Y (termed second order decode), and multiply the decoded result by the multiplicand X for producing one partial product. Finally, 27 partial products from the partial products 0 to 26 are produced. The sorts of the partial products are determined by the three-digit pattern of the multiplier Y as shown in FIG. 7. FIG. 7 shows the relation among the inputs to the Booth decoder, the sorts of the partial products, and the bit sequences. For example, when the three digits of the multiplier is 011, the partial product is a double of the multiplicand, that is, the multiplicand shifted by one to left. When the three digits of the multiplier is 100, the partial product is the multiplicand multiplied by -2, that is, the multiplicand that is represented in two's complement and shifted by one to left.
Each sort of partial product is represented by a 53-digit X (implicit `1`, X1, X2, . . . , X52 ranged in sequence from the leftmost position). As noted above, since the partial product is represented in two's complement, the two sorts of partial products, the multiplicand multiplied by -1 and the multiplicand multiplied by -2, are represented by the negatives of X bits and `1` to be added to the least significant bit. Each partial product is a 54-digit bit sequence. The digits having the same weight contained in the bit sequence, that is, the digits at the same position from the floating point are added to each other for obtaining the result.
However, when adding a number having a greater digits upper than the most significant digit of a negative partial product to the negative partial product such as the multiplicand multiplied by -0, -1, or -2 (hereafter termed in mathematical expression like -0 times multiplicand, -1 times multiplicand, -2 times multiplicand), a sign correction is executed for the digits upper than the most significant digit of the negative partial product. (For example, when the negative partial product consists of four bits and is 1101 (-3), the four-bit sign correction is executed for the upper significant digits for deriving the resulting 8-bit value, concretely, 11111101). Then, the addition is executed for all digits containing the sign correction digits. Hence, when adding the partial products, as shown in FIG. 8, the addition is required to perform for the portion including the sign correction portion.
As means for adding the partial products shown in FIG. 8, a carry save addition is used. As shown in FIG. 10, the carry save adder gives rise to two kinds of outputs, sum and carry. As to the output of the carry, the carry may be negative, that is, the carry may contain digits left of the most significant digit of the partial product. Then, consider the carry propagate addition of two outputs from the carry save adder and a third number. In case that the third number has digits upper than the most significant digit of the carry save adder and the carry is negative, the sign correction is executed to fill with `1` the left digits of the most significant digit of the carry. The addition has to be done for all digits containing the sign correction digits. Hence, it is necessary to apply the carry propagate adder to all digits as shown in FIG. 10.
The conventional partial product adder is shown in FIG. 34. A multiplier 3210 is applied to a Booth decoder 3201 and a least significant digit generator 3203. The multiplicand 3211 is applied to a Booth selector 3202. The Booth decoder 3201 generates a Booth decode signal 3212 from the multiplier 3210. The Booth selector 3202 generates a signal 3214 for representing a partial product from the Booth decode multiplicand 3211 and the signal 3212. The least significant digit generator 3203 generates a signal for representing the least significant digit to be added for generating a two's complement.
A numeral 3204 denotes a sign correction generator 3204, which generates a signal 3215 for representing the sign correction portion shown in FIG. 8 from the Booth decode signal 3212. A numeral 3205 denotes a carry save adder, which performs a carry save addition of the digits having the same weights contained in the signals 3213, 3214 and 3215, for generating a sum 3216 and a carry 3217 of the partial product addition.
The conventional floating point multiplying apparatus is shown in FIG. 33. In this multiplying apparatus, a Booth decoder 3201, a Booth selector 3202, a least significant digit generator 3203, a sign correction generator 3204, and a carry save adder 3205 are the same as those described with reference to FIG. 34. A numeral 3306 denotes a carry propagate adder, which performs a carry propagate addition of the signals 3216 and 3217 and outputs a signal 3318. A numeral 3307 denotes a normalizing and rounding unit, which normalizes and rounds the signal 3318 and outputs the resulting signal 3319 of the multiplying apparatus.
The conventional floating point operating unit for sum of products is shown in FIG. 32. In the summing unit, a Booth decoder 3201, a Booth selector 3202, a least significant digit generator 3203, a sign correction generator 3204, and a carry propagate adder 3205 are the same as the foregoing components. The carry propagate adder 3206 performs a carry propagate addition o the signals 3216 and 3217 and a third number 3218 containing the sign correction digits shown in FIG. 10 for generating a signal 3219. Then, a normalizing and rounding unit 3207 normalizes and rounds the signal 3219 and output the resulting signal 3220 of the operating unit for a sum of products.
In turn, the description will be oriented to the conventional detection of the most significant digit (leftmost digit).
Consider a rounding unit commonly used for a multiplying apparatus for treating a number of an IEEE double-precision format and a number of an IEEE single-precision format. The match of a rounding position between the single-precision number and the double-precision number results in making the positions of the most significant digits different from each other. In overcoming this drawback, it is necessary to provide a step of determining the most significant digit. An example of the method for detecting the most significant digit is disclosed in JP-A 5-265714. As to the different precision floating point numbers, the respective most significant digits are positioned differently after the addition of the partial products. Hence, a circuit for selecting the most significant digit is added for overcoming the drawback resulted from the variety of the precisions.
FIG. 35 shows the conventional floating point multiplying apparatus additionally provided with the circuit for selecting the most significant digit. A partial product generator 3501 generates a signal 3512 for representing a partial product from a multiplicand 3511 and a multiplier 3510. A carry save adder 3502 performs a carry save addition of the signal 3512 for deriving two output signals 3513 and 3514. A carry propagate adder 3503 performs a carry save addition of the signals 3513 and 3514 and generates the signal 3515 for representing a double-precision most significant digit and a single-precision most significant digit and the added result signal 3516.
A selector 3504 receives a signal 3517 for representing execution of the single-precision multiplication, its inverted signal 3518, and the double-precision and single-precision most significant digit signal 3515 and outputs a signal 3519 representing the single-precision most significant digit if the single-precision multiplication is currently executed or the double-precision most significant digit if the double-precision multiplication is currently executed. A normalizing and rounding unit 3505 receives the added result signal 3516 and the signal 3519, normalizes and rounds the signals, and then outputs the multiplied result (fraction) signal 3520.
Next, the conventional normalizing shift will be described below.
Consider the following carry propagate addition of the fraction. The carry propagate addition is executed after dividing the fraction into upper half digits and lower half digits. Two addition of the upper half digits are performed according to the carry from the lower half digits, concretely, one addition of the upper half digits for the case that a carry from the lower half digits exists and the other addition for the case that no carry from the lower half digits exists. One of the addition results is selected based on the actual carry. In this case, the normalizing shift is controlled using the the most significant digit of the addition result selected based on the carry from the lower half digits.
FIG. 36 shows this sort of floating point multiplying apparatus of the prior art. A numeral 3601 denotes a partial product generator and carry save adder, both of which operate to generate a partial product from a multiplier 3612 and a multiplicand 3612 and perform a carry save addition about the partial products for feeding a sum signal 3613 and a carry signal 3614. An upper half digit adder (A+B) 3602 adds the upper digits A of the signal 3613 to the upper digits B of the signal 3614 and feed a signal 3615 that corresponds to a carry propagate addition if no carry from the lower half digits exists. An upper half digit adder (A+B+1) 3603 adds the upper digits A of the signal 3613 to the upper digits B of the signal 3614 and `1` and feeds a signal 3616 that corresponds to a carry propagate addition if any carry from the lower half digit exists. A lower half digit adder 3604 adds the lower digits of the signal 3613 to the lower digits of the signal 3614 for generating a carry signal 3617.
An added result selector 3605 selects the signal 3515 or 3616 based on a carry signal 3617 and feeds the most significant digit signal 3618 and the signal 3619. A normalizing unit 3606 performs a normalizing shift on the signal 3619 using the most significant digit signal 3618 as a control signal and feeds a multiplied result (fraction) signal 3620.
As described above, the use of the Booth algorithm for the addition of partial products advantageously results in reducing the hardware amount used for the addition of partial products because of the reduction of the partial products in number. Disadvantageously, however, the hardware needs to have an additional sign correction section. Hence, the additional hardware of the sign correction section offsets the effective reduction of the hardware to some extent.
As to the sum of productions, since the sign correction portion of the partial product needs to be added, it is necessary to execute the sign correction for the most significant digit of the carry outputted from the carry save adder and perform addition including the sign correction digits.
As mentioned above, the most significant digit is obtained after the carry is propagated from the least significant digit. Hence, the propagation may make the delaying time longer and thereby is a critical path of the multiplying apparatus. As in the prior art, if the most significant digit detector is used for detecting the most significant digit in the multiplying apparatus that treats the floating point numbers whose precisions are variable to each other, this arrangement may disadvantageously increase the delaying time further and needs a more time for the critical path of the multiplying apparatus.
The normalizing shift control signal used for the conventional normalizing shift is the most significant digit selected according to the carry from the lower half digits. Hence, the most significant digit that needs longer delaying time due to the relevant fan-out in scale, thereby extending the delaying time of the path passing through the most significant digit.